#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define NAME_SIZE    32
#define FUNC_LEN    4096
#define FUNC_NUM    32

struct Func_t {
    char name[NAME_SIZE];
    char code[FUNC_LEN];
    bool init;
    bool flag;
    struct Func_t *next;
    struct Func_t *prev;
};


/* ----------------- wt.h ---------------- */
// 初始化单词表
void initWordTable(const char *filename);

// 查找单词表
// return value: 查找的结果，找到的话返回找到单词的指针，没找到返回NULL
char *searchWord(char *word);

/* ----------------- parser.h ------------------ */
void initSym();

void start_op();

bool funcHead(char c);

bool funcChar(char c);

char *addSymbol(char *line);

char *getKeyInfo(struct Func_t *header);


/* ----------------- editdistDP.h ---------------------- */
int editdistDP(char *, char *);

/* ----------------- main.c --------------- */

#define WORD_FILE    "keepwords.txt"
#define DEBUG_FILE    "debuginfo.txt"
#define CODE_FILE    "codes.txt"
#define CODES_NUM    256
#define LINE_SIZE    512

void getAns(char **arr);

void cleanFunArr(struct Func_t *header);

int
main() {
    initWordTable(WORD_FILE);
    // printf("init word table over\n");
    // initSym();
    // printf("init Sym over\n");
    // 打开 "codes.txt"
    FILE *fp = NULL;
    fp = fopen(CODE_FILE, "r");
    if (fp == NULL) {
        fprintf(stderr, "open file %s error\n", CODE_FILE);
        exit(1);
    }

    // Debug File
    FILE *dp = NULL;
    dp = fopen(DEBUG_FILE, "w");
    if (dp == NULL) {
        fprintf(stderr, "open file %s error\n", DEBUG_FILE);
        exit(1);
    }

    // KeyInfo 数组
    char **keyInfoArr = (char **) calloc(CODES_NUM, sizeof(char *));
    if (keyInfoArr == NULL) {
        fprintf(stderr, "error malloc size: %lu\n", sizeof(char *) * CODES_NUM);
        exit(1);
    }

    int infoIndex = 0;            // KeyInfo索引指针
    char line[LINE_SIZE];        // 缓冲区
    int i, j = 0;
    while (!feof(fp)) {
        // 读取一个源文件
        // start_op();
        struct Func_t *header = (struct Func_t *) calloc(1, sizeof(struct Func_t));
        struct Func_t *ptr;
        int func_begin = 0;
        j = 0;

        char *c = line;
        while (!(*c >= '0' && *c <= '9') && !feof(fp)) {
            fgets(line, LINE_SIZE, fp);
        }
        if (feof(fp)) break;

        for (j = 0; line[j] >= '0' && line[j] <= '9'; j++) {
            header->code[j] = line[j];
        }
        header->flag = true;
        header->init = true;

        ptr = (struct Func_t *) calloc(1, sizeof(struct Func_t));
        header->next = ptr;
        ptr->prev = header;


        while (fgets(line, LINE_SIZE, fp) != NULL) {
            // printf("%s\n", line);
            // 源文件结束符
            if (line[0] == '\f') break;

            if (line[0] == '\n') continue;

            char *temp = line;
            // 可能是一个函数开头
            if (func_begin == 0) {
                int k = 0;
                do {
                    while (!funcHead(line[k]) && line[k] != '\0') k++;
                    if (line[k] == '\0') {
                        fgets(line, LINE_SIZE, fp);
                        k = 0;
                        if (line[0] == '\f') break;
                    }
                } while (!funcHead(line[k]));
                if (line[0] == '\f') break;
                // 如果添加到符号表中，以方便之后处理，不将这个函数声明放入缓冲区
                for (j = 0; funcChar(line[k]); j++) {
                    ptr->name[j] = line[k++];
                }
                ptr->name[j] = '\0';
                // 把函数声明中的参数部分找到
                int cnum = 0;
                do {
                    for (; line[k] != '(' && line[k] != '\0'; k++);
                    if (line[k] == '\0') {
                        fgets(line, LINE_SIZE, fp);
                        k = 0;
                    }
                } while (line[k] != '(');
                k++;
                cnum += 1;
                while (cnum != 0) {
                    switch (line[k]) {
                        case '(':
                            cnum++;
                            break;
                        case ')':
                            cnum--;
                            break;
                        case '\0':
                            fgets(line, LINE_SIZE, fp);
                            k = 0;
                            break;
                        default:
                            break;
                    }
                    k++;
                }

                // 找到第一个大括号
                do {
                    for (; line[k] != '{' && line[k] != '\0'; k++);
                    if (line[k] == '\0') {
                        fgets(line, LINE_SIZE, fp);
                        k = 0;
                    }
                } while (line[k] != '{');
                j = 0;

                temp = &line[k];
                ptr->flag = false;
                ptr->init = true;
                ptr->next = NULL;
            }

            for (i = 0; temp[i] != '\0'; i++) {
                if (temp[i] == '{') {
                    func_begin += 1;
                } else if (temp[i] == '}') {
                    func_begin -= 1;
                    if (func_begin == 0) {
                        ptr->code[j++] = temp[i];
                        // 一个函数结束
                        ptr->code[j] = '\0';
                        struct Func_t *f = (struct Func_t *) calloc(1, sizeof(struct Func_t));
                        ptr->next = f;
                        f->flag = false;
                        f->next = NULL;
                        f->prev = ptr;
                        f->init = false;
                        ptr = f;
                        continue;
                    }
                }
                if (temp[i] != '\r' && temp[i] != '\t') {
                    ptr->code[j++] = temp[i];
                }
            }
        }
        if (header->init) {
            char *keyinfo = getKeyInfo(header);
            // printf("%s\n", keyinfo);
            keyInfoArr[infoIndex++] = keyinfo;
            fprintf(dp, "%s\n", keyinfo);
        }
        cleanFunArr(header);
    }

    getAns(keyInfoArr);

    fclose(fp);
    fclose(dp);
    return 0;

}

void
cleanFunArr(struct Func_t *h) {
    struct Func_t *p = h, *t;
    while (p != NULL) {
        t = p->next;
        free(p);
        p = t;
    }
}

struct Group_t {
    int num;
    char *arr[1024];
};

int gI;                // 索引
struct Group_t Group[CODES_NUM];

double tValue = 0.95;
char flag[128];

void
getAns(char **arr) {

    // 第一个程序的鉴定
    int index = 0;
    int nindex = index + 1;

    int len1 = strlen(arr[index]);
    int len = len1;
    Group[0].arr[Group[0].num++] = arr[0];
    char name[7];
    for (nindex = index + 1; arr[nindex] != NULL; nindex++) {
        int len2 = strlen(arr[nindex]);
        int K = editdistDP(arr[index] + 6, arr[nindex] + 6);
        len = len1 > len2 ? len1 : len2;
        len -= 6;
        double value = 1.0 - ((double) K / (double) len);
        // printf("K: %d value: %f\n", K,  value);
        if (value > tValue) {
            Group[gI].arr[Group[gI].num++] = arr[nindex];
            flag[nindex] = 1;
        }
    }

    gI++;
    index = 1;

    int i, j;

    while (arr[index] != NULL) {
        // 判断是否在上一个集合里
        // printf("%d: ", index);
        if (flag[index] == 1) {
            index++;
            continue;
        }

        flag[index] = 1;
        Group[gI].arr[Group[gI].num++] = arr[index];
        char name[7];
        strncpy(name, arr[index], 6);
        name[6] = '\0';
//        printf("check: %s\n", name);

        // printf("%d: %p\n", index, arr[index]);
        int len = strlen(arr[index]);
        for (nindex = index + 1; arr[nindex] != NULL; nindex++) {
            if (flag[nindex] == 1)
                continue;
            // printf("%p\n", arr[nindex]);
            char _name[7];
            strncpy(_name, arr[nindex], 6);
            _name[6] = '\0';
//            printf("%s ", _name);
            int len2 = strlen(arr[nindex]);
            int K = editdistDP(arr[index] + 6, arr[nindex] + 6);
            len = len1 > len2 ? len1 : len2;
            len -= 6;
            double value = 1.0 - ((double) K / (double) len);
            // printf("K: %d value: %f\n", K,  value);
            if (value >= tValue) {
                Group[gI].arr[Group[gI].num++] = arr[nindex];
                flag[nindex] = 1;
            }
        }
//        printf("\n");
        index++;
        gI++;
    }
    // printf("gi: %d\n", gI);
    for (j = 0; j < gI; j++) {
        if (Group[j].num > 1) {
            for (i = 0; i < Group[j].num; i++) {
                Group[j].arr[i][6] = '\0';
                printf("%s ", Group[j].arr[i]);
            }
            printf("\n");
        }
    }
}


/* --------------------- wt.c ----------------------- */
struct WT_t {
    char *word;
    struct WT_t *next;
};

struct WT_t WT[25];


void
initWordTable(const char *filename) {
    FILE *fp = NULL;
    fp = fopen(filename, "r");
    if (fp == NULL) {
        fprintf(stderr, "open file %s error\n", filename);
        exit(1);
    }

    char buf[32];
    int index = 0, temp = 0;
    int len = 0;
    char *word = NULL;
    struct WT_t *wt, *wtp;
    while (!feof(fp)) {
        wt = (struct WT_t *) calloc(1, sizeof(struct WT_t));
        wt->word = NULL;
        wt->next = NULL;
        fscanf(fp, "%s", buf);
        // strdup 在测评环境下有异常
        len = strlen(buf);
        word = (char *) calloc(len, sizeof(char));
        for (int i = 0; i < len; i++) {
            word[i] = buf[i];
        }

        if (word[0] == '_') {
            index = 24;
        } else {
            index = (word[0] >= 'a' && word[0] <= 'z') ? word[0] - 'a' : word[0] - 'A';
        }
        wtp = &WT[index];
        for (; wtp->word != NULL; wtp = wtp->next);
        wtp->word = word;
        wtp->next = wt;
    }
    fclose(fp);
    fp = NULL;
}

char *
searchWord(char *word) {
    int index = 0, temp = 0;
    if (word[0] == '_') {
        index = 24;
    } else {
        index = (word[0] >= 'a' && word[0] <= 'z') ? word[0] - 'a' : word[0] - 'A';
    }
    struct WT_t *wt = &WT[index];
    while (wt->next != NULL) {
        if (strcmp(wt->word, word) == 0)
            return wt->word;
        wt = wt->next;
    }
    return NULL;
}


/* ------------------ parser.c -------------------- */

#define KEY_SIZE    2048
#define SYM_SIZE    32
#define SYM_NUM        1024

bool
isEn(char c) {
    return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}

bool
funcHead(char c) {
    return (c == '_' || isEn(c));
}

bool
funcChar(char c) {
    return (funcHead(c) || (c >= '0' && c <= '9'));
}

char **Symbols;
int end;
int begin;

void
initSym() {
    Symbols = (char **) malloc(sizeof(char *) * SYM_NUM);
    begin = 0;
    end = 0;
}

void
start_op() {
    begin = end;
}

char *
addSymbol(char *line) {
    char buf[SYM_SIZE];
    char *ptr = line, *b = buf;
    while (funcChar(*ptr)) {
        *b = *ptr;
        b++;
        ptr++;
    }
    *b = '\0';
    while (*ptr == ' ' || *ptr == '\n' || *ptr == '\r' || *ptr == '\t')
        ptr++;
    if (*ptr != '(') {
        return NULL;
    }
    // printf("%s\n", buf);
    char *ret = ptr;
    while (*ret != ')') ret++;
    int len = strlen(buf);
    Symbols[end] = (char *) malloc(sizeof(char) * len);
    ptr = buf;
    b = Symbols[end];
    while (*ptr != '\0') {
        *b = *ptr;
        b++;
        ptr++;
    }
    *b = '\0';
    end++;
    return ++ret;
}

char *
isMFunc(char *word) {
    int i = 0;
    // printf("Match %s:\n", word);
    for (i = begin; i < end; i++) {
        // printf("%s\n", Symbols[i]);
        if (strcmp(word, Symbols[i]) == 0) {
            return Symbols[i];
        }
    }
    return NULL;
}

void
deleteF(struct Func_t *f) {
    if (f->prev != NULL) {
        f->prev->next = f->next;
    }
    if (f->next != NULL) {
        f->next->prev = f->prev;
    }
    f->prev = NULL;
    f->next = NULL;
}

void
connectF(struct Func_t *p, struct Func_t *n) {
    n->next = p->next;
    if (p->next != NULL) {
        p->next->prev = n;
    }
    n->prev = p;
    p->next = n;
}

char *
getKeyInfo(struct Func_t *funcArr) {

    char *ret = (char *) malloc(sizeof(char) * KEY_SIZE);
    char *ptr;
    char buf[SYM_SIZE];
    int j = 0;            // buf指针
    int i = 0;            // ret指针
    struct Func_t *p = funcArr, *t = NULL;

    // 找到main函数
    while (p->next != NULL) {
        // printf("%s\n", p -> name);
        if (strcmp(p->name, "main") == 0)
            break;
        p = p->next;
    }
    // funcArr -> 序号
    // p -> main
    deleteF(p);
    connectF(funcArr, p);
    ptr = p->code;
    p->flag = true;
    // printf("%s:\n", funcArr-> code);
    while (*ptr != '\0') {
        if (funcHead(*ptr)) {
            j = 0;
            while (funcChar(*ptr) && *ptr != '\0') {
                buf[j++] = *ptr;
                ptr++;
            }
            if (*ptr != '(')
                continue;
            buf[j] = '\0';
            t = funcArr;
            for (; t->init; t = t->next) {
                // printf("t-> next: %p\n", t-> next);
                if (!t->flag && strcmp(t->name, buf) == 0) {
                    // printf("%s\n", t -> name);
                    deleteF(t);
                    connectF(p, t);
                    p = t;
                    t->flag = true;
                    break;
                }
            }

        } else {
            ptr++;
        }
    }

    p = funcArr;
    while (p != NULL && p->init) {
        if (p->flag == false) {
            p = p->next;
            continue;
        }

        ptr = p->code;
        p = p->next;
        while (*ptr != '\0') {
            if (funcHead(*ptr)) {
                j = 0;
                while (funcChar(*ptr)) {
                    buf[j++] = *ptr;
                    ptr++;
                }
                buf[j] = '\0';
                if (strcmp(buf, "main") == 0) {
                    strcpy(ret + i, "main");
                    i += 4;
                    memset(buf, 0, strlen(buf));
                    continue;
                }


                char *name = NULL;
                for (t = funcArr; t->init; t = t->next) {
                    if (strcmp(t->name, buf) == 0) {
                        name = t->name;
                        break;
                    }
                }

                // printf("%s\n", buf);
                if (name != NULL) {
                    // printf("%s\n", name);
                    strcpy(ret + i, "FUNC");
                    i += 4;
                    memset(buf, 0, strlen(buf));
                    continue;
                }
                name = searchWord(buf);
                if (name != NULL) {
                    strcpy(ret + i, name);
                    i += strlen(name);
                    memset(buf, 0, strlen(buf));
                    continue;
                }
                memset(buf, 0, strlen(buf));
            } else {
                if (*ptr != '\n' && *ptr != ' ' && *ptr != '\r' && *ptr != '\t') {
                    ret[i++] = *ptr;
                    if (*ptr == '0') {
                        // 判断是否是0xfff这样的十六进制
                        char *temp = ptr + 1;
                        if (*temp == 'x' || *temp == 'X') {
                            ret[i++] = *temp++;
                            // 十六进制数
                            while ((*temp <= '9' && *temp >= '0') || (*temp <= 'F' && *temp >= 'A') ||
                                   (*temp <= 'f' && *temp >= 'a')) {
                                ret[i++] = *temp;
                                temp++;
                            }
                            ptr = temp - 2;
                        }
                    }
                }
                ptr++;
            }
        }
    }
    ret[i] = '\0';
    return ret;
}

#define max2(a, b) ((a)>(b)?(a):(b))
int **Dp, MaxDP = 3300;                                //for dynamic programming
int min3(int a, int b, int c) {
    int min = a < b ? a : b;
    return min < c ? min : c;
}

int error2(char *s) {
    fprintf(stderr, "%s\n", s);
    exit(-1);
}

int initDP() {
    int i;
    Dp = (int **) malloc(MaxDP * sizeof(int *));
    // printf("init\n");
    for (i = 0; i < MaxDP; i++)
        Dp[i] = (int *) malloc(MaxDP * sizeof(int));
    return 0;
}

int editdistDP(char *str1, char *str2) {
    int i, j;
    static int flag = 0;
    int len1, len2;
    len1 = strlen(str1) + 1;
    len2 = strlen(str2) + 1;
    (flag++) ? 1 : initDP();
    (max2(len1, len2) >= MaxDP) ? error2("DP memory error!") : len1;
    for (i = 0; i <= len1; i++) {
        for (j = 0; j <= len2; j++) {
            if (i == 0)
                Dp[i][j] = j;
            else if (j == 0)
                Dp[i][j] = i;
            else if (str1[i - 1] == str2[j - 1])
                Dp[i][j] = Dp[i - 1][j - 1];
            else
                Dp[i][j] = 1 + min3(Dp[i][j - 1], Dp[i - 1][j], Dp[i - 1][j - 1]);
        }
    }
    return Dp[len1][len2];
}

